/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package p1;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;

/**
 *
 * @author Derek Ward
 * 
 * Represents a problem which has been inputted.
 * Solves it in one of three ways.  
 * 
 * The main work for the project is in here.
 * 
 * I used the Dijkstra pathing algorithm for all
 * of the solutions.
 * 
 * Problem 1).  This is a simple implementation of
 *              the Dijkstra algorithm.
 * 
 * Problem 2).  I approached this problem (and the
 *              the next problem) by using the 
 *              Dijkstra algorithm multiple times,
 *              going from node to node and 
 *              checking for node overlaps.  This
 *              is repeated 2^(n-1) times with
 *              random arrangements to find the
 *              most optimal path.
 * 
 * Problem 3).  Is just a variation of Problem 2.
 * 
 */
public class Problem 
{
    private     ArrayList<String>       m_cities;
    private     int                     m_problemID;
    private     Graph                   m_graph;
    
    public Problem(ArrayList<String> cities, int pID)
    {
        if ( cities != null )
            m_cities = cities;
        else
            throw new NullPointerException("Problem::Problem(ArrayList<String>, int) was passed a null ArrayList<String> (cities)!");
        
        if ( pID <= 3 && pID >= 1 )
            m_problemID = pID;
        else
            throw new IllegalArgumentException("Problem::Problem(ArrayList<String>, int) was passed a Problem ID with an invalid range (pID)!");
    }
    
    public void solveProblem(Graph g) throws InvalidProblemException
    {
        if (g != null)
            m_graph = g;
        else
            throw new NullPointerException("Problem::solveProblem(Graph) was passed a null Graph object (g)!");
        
        switch (m_problemID)
        {
            case 1:
                solveProblem1();
                break;
            case 2:
                solveProblem2();
                break;
            case 3:
                solveProblem3();
                break;
            default:
                throw new InvalidProblemException("ProblemFile::solveProblem(Graph) expected a number within the proper range for this problem (1 - 3)!");
        }
    }
    
    /*
     * 1: there are two strings and the question is to find the shortest path 
     * between
     */
    private void solveProblem1() throws InvalidProblemException
    {
        Node    source = m_graph.getNode(m_cities.get(0));
        Node    target = m_graph.getNode(m_cities.get(1));
        
        if ( m_cities.size() != 2)
            throw new InvalidProblemException("ProblemFile::solveProblem1() expected a cities ArrayList with a size of 2!");
        
        //System.out.println("solveProblem1");
        
        dijkstra(source, target, false);
        
        //m_graph.printGraph();
        
        //printShortestPath(source, target, false);
        Solution s = new Solution(source, target);
        System.out.println(s);
    }
    
    /*
     * 2: there are >2 strings and the problem is to find shortest path from the 
     * first string to all the other strings (in any order, possibly visiting other nodes)
     * 
     * This could be solved by starting with the first node, using dij. to the second node,
     * second to third, etc.; then trying different combinations.  This might take a while, 
     * but it should be complete.
     */
    private void solveProblem2() throws InvalidProblemException
    {
        Node                    source, dest;
        ArrayList<Solution>     solutions = new ArrayList<Solution>();
        Solution                latestSolution;
        boolean                 purgedACity;
        int                     bestSolutionWeight = Integer.MAX_VALUE;
        int                     tempTotalWeight;
        ArrayList<Solution>     bestSolutions = null;
        ArrayList<String>       tempCities;
        
        if ( m_cities.size() < 2)
            throw new InvalidProblemException("ProblemFile::solveProblem2() expected a cities ArrayList with a size of at least 2!");

        for ( int t = 0; t < Math.pow(2.0, (double) m_cities.size() - 1); t++ )
        {
            tempCities = copyCitiesList();
            
            source = m_graph.getNode(tempCities.get(0));

            for ( int i = 0; i < (tempCities.size() - 1); )
            {
                dest   = m_graph.getNode(tempCities.get(i + 1));

                dijkstra(source, dest, false);

                latestSolution = new Solution(source, dest);

                if ( !latestSolution.isSolutionGood() )
                {
                    System.out.println("Route is not possible due to solution with node: " + latestSolution.toString());
                    return;
                }

                solutions.add(latestSolution);

                if ( purgeCityList(latestSolution, dest.getLabel(), tempCities) )
                    purgedACity = true;
                else
                    purgedACity = false;

                source = dest;

                m_graph.resetNodeValues();

                if ( purgedACity )
                    i = 0;
                else
                    i++;
            }
            
            tempTotalWeight = getSolutionsTotalWeight(solutions);
            
            if ( tempTotalWeight < bestSolutionWeight )
            {
                bestSolutions = copySolutions(solutions);
                bestSolutionWeight = tempTotalWeight;
            }
            
            solutions.clear();
            
            randomizeCityList();
        }
        
        printSolutionSet(bestSolutions);
    }
    
    /*
     * 3: only one string, and the problem is to find shortest path from this 
     * node to all others.
     * 
     * Basically a type of problem2.
     */
    private void solveProblem3() throws InvalidProblemException
    {
        if ( m_cities.size() != 1)
            throw new InvalidProblemException("ProblemFile::solveProblem3() expected a cities ArrayList with a size of 1!");

        // Populate m_cities with every node in the graph, except
        // for the one that's already in m_cities (ie. the start)
        
        for ( Node n : m_graph.getNodeList() )
        {
            if ( !m_cities.get(0).equals(n.getLabel()) )
                m_cities.add(n.getLabel());
        }
        
        //System.out.println(m_cities);
        
        solveProblem2();
    }
    
    /*
     * Simple implemenation of the Dijkstra algorithm
     */
    private void dijkstra(Node s, Node t, boolean limit)
    {
        double              td;
        Node                tn, dn;
        PriorityQueue<Node> nq = new PriorityQueue<Node>();
        s.m_min = 0.0;
        nq.add(s);
        
        while ( !nq.isEmpty() )
        {
            tn = nq.poll();
            
            if ( t != null && t.getLabel().equals(tn.getLabel()) )
                return;
            
            for (Edge e : tn.m_connectedEdges)
            {
                if ( tn.getLabel().equals(e.getDestinationNode().getLabel()) )
                    dn = e.getSourceNode();
                else
                    dn = e.getDestinationNode();
                
//                if ( limit && !m_cities.contains(dn.getLabel()) )
//                    continue;
                
                td = tn.m_min + e.getWeight();
                if ( td < dn.m_min )
                {
                    nq.remove(dn);
                    dn.m_min = td;
                    dn.m_previousNode = tn;
                    nq.add(dn);
                }
            }
        }
    }
    
    /*
     * NOTE:  Remove all but the current node label!!!
     */
    private boolean purgeCityList(Solution s, String currentLocationLabel, ArrayList<String> citiesList)
    {
        ArrayList<String>   solutionLabelList = s.getNodeLabelList();
        boolean             didWePurgeAnything = false;
        
        for ( int i = 0; i < solutionLabelList.size(); i++ )
        {
            if ( citiesList.contains(solutionLabelList.get(i)) &&
                 !solutionLabelList.get(i).equals(currentLocationLabel))
            {
                citiesList.remove(solutionLabelList.get(i));
                didWePurgeAnything = true;
            }
        }
        
        return didWePurgeAnything;
    }
    
    /*
     * Randomize m_cities, except for the first entry
     */
    private void randomizeCityList()
    {
        Random              rand = new Random();
        List<String>        randomBin = m_cities.subList(1, m_cities.size());
        ArrayList<String>   newCitiesList = new ArrayList<String>();
        
        newCitiesList.add(m_cities.get(0));
        
        while ( randomBin.size() > 0)
        {
            int r = rand.nextInt(randomBin.size());
            
            newCitiesList.add(randomBin.get(r));
            randomBin.remove(r);
        }
        
        m_cities = newCitiesList;
    }
    
    private void printSolutionSet(ArrayList<Solution> sl)
    {
        int     totalWeight = getSolutionsTotalWeight(sl);
        
        if ( totalWeight == -1 )
        {
            return;
        }
        
        System.out.print(totalWeight + " " + sl.get(0).toStringSansTotal());
        
        for ( int i = 1; i < (sl.size()); i++ )
            System.out.print(sl.get(i).toStringSansTotalSansFirst());
        
        System.out.println();
    }
    
    private int getSolutionsTotalWeight(ArrayList<Solution> sl)
    {
        int     totalWeight = 0;
        
        for ( Solution s : sl )
        {
            if ( s.getSolutionWeight() == -1 )
            {
                System.out.println("Route is not possible due to solution with node: " + s.toString());
                return -1;
            }
            totalWeight += s.getSolutionWeight();
        }
        
        return totalWeight;
    }
    
    private ArrayList<String> copyCitiesList()
    {
        ArrayList<String> tal = new ArrayList<String>();
        
        for ( String s : m_cities )
            tal.add(s);
        
        return tal;
    }
    
    private ArrayList<Solution> copySolutions(ArrayList<Solution> sl)
    {
        ArrayList<Solution> tsl = new ArrayList<Solution>();
        
        for ( Solution s : sl )
            tsl.add(s.clone());
        
        return tsl;
    }
}
